MERGE SORT - The Sorting Algorithm

MERGE SORT

Merge Sort Is A type Of Algorithm Used To Sort Array/Lists. Merge Sort Is A Divide And Conquer Algorithm. In Merge Sort, The Unsorted Array Is Divided Into Half SubArrays Recursively Until There Is Only 1 Element Remaining After Which Right And Left SubArrays Are Sorted And Recursively Merged Until The Whole Array Is Sorted. Merge Sort Is The Best Sorting Algorithm Compared To All The Other Sorting Algorithm.

COMPLEXITY

Worst complexity: n*log(n)

Average complexity: n*log(n)

Best complexity: n*log(n)

Space complexity: n

IMPLEMENTATION

C++

#include<iostream>
#include<stdio.h>
#include<string.h>

using namespace std;

void Merge(int a[], int begin, int mid, int end)
{
    int n1 = mid - begin + 1;
    int n2 = end - mid;
    
    int l[n1];
    int r[n2];
    
    for(int i=0; i<n1; i++)
    {
        l[i] = a[begin+i];
    }
    for(int m=0; m<n2; m++)
    {
        r[m] = a[mid + 1 +m];
    }
    
    
    int j =0;
    int k=0;
    int q=begin;
    
    while(j<n1 && k<n2)
    {
        if(l[j]<=r[k])
        {
            a[q] = l[j];
            j = j+1;
            q=q+1;
        }
        else if(l[j]>=r[k])
        {
            a[q] = r[k];
            k = k+1;
            q = q+1;
        }
    }
    
    while(j<n1)
    {
        a[q] = l[j];
        j=j+1;
        q = q+1;
    }
    
    while(k<n2)
    {
        a[q] = r[k];
        k = k+1;
        q = q+1;
    }
    
}

void MergeSort(int a[], int begin, int end)
{
if(begin<end)
{

    int mid = begin+(end-begin)/2;
    MergeSort(a,begin,mid);
    MergeSort(a,mid+1,end);
    
    Merge(a,begin,mid,end);
    
}
}

void PrintArray(int a[],int size)
{
    for(int i=0; i<size;i++)
    {
        cout<<a[i];
        cout<<"\n";
       
    }
}

int main() {

    int a[] = {6,5,4,3,2,1,4,3,2,1,8,9,0,7,6,12,11,10};
    int size = sizeof(a)/sizeof(a[0]);
    MergeSort(a,0,size-1);
    PrintArray(a,size);
    
}

JAVA

public class MyClass {
    
    static void Merge(int a[],int begin, int mid,int end)
    {
        int n1 = mid - begin + 1;
        int n2 = end - mid;
        
        int[] L = new int[n1];
        int[] R = new int[n2];
        
        for(int i=0; i<n1; i++)
        {
            L[i] = a[begin+i];
        }
        
        for(int i=0;i<n2; i++)
        {
            R[i] = a[mid+1+i];
        }
        
        int i =0;
        int j=0;
        int k = begin;
        
        while(i<n1 && j<n2)
        {
            if(L[i]<=R[j])
            {
                a[k]=L[i];
                i++;
                k++;
            }
            else if(L[i]>=R[j])
            {
                a[k] = R[j];
                j++;
                k++;
            }
        }
        
        while(i<n1)
        {
            a[k] = L[i];
            i++;
            k++;
        }
        
        while(j<n2)
        {
            a[k] = R[j];
            j++;
            k++;
        }
        
    }
    
    
    static void MergeSort(int a[],int begin,int end)
    {
        if(begin<end)
        {
            int mid = (begin+end)/2;
            MergeSort(a,begin,mid);
            MergeSort(a,mid+1,end);
            Merge(a,begin,mid,end);
        }
        
    }
    
    static void PrintArray(int a[],int size)
    {
        for(int i:a)
        {
            System.out.println(i);
        }
    }
    
    
    public static void main(String args[]) {
      int a[] = {6,5,4,3,2,1,4,3,2,1,8,9,0,7,6,12,11,10};
      int size = a.length;
      
      MergeSort(a,0,size-1);
      PrintArray(a,size);
    }
}